НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КАФЕДРА ПРИКЛАДНОЇ МАТЕМАТИКИ
Конспект лекцій з курсу
“МЕТОДИ ОПТИМІЗАЦІЇ”
( для студентів ІІІ курсу
Інституту прикладної математики та фундаментальних наук)
Підготувала
доцент кафедри ПМ
Уханська О.М.
2003
ВСТУП
Під задачами оптимізації підрозумівають будь-які задачі, переважно економічного характеру, в яких шукаються екстремуми функцій або функціоналів. Суть цих задач полягає в тому, щоб із множини можливих варіантів досліджуваного процесу вибрати за деякою ознакою найкращий (оптимальний) варіант.
Задачі оптимізації можна поділити на такі види:
задачі математичного програмування;
задачі варіаційного числення;
задачі оптимального управління.
Кожна велика система – фінансові чи банківські організації, великі промислові підприємства, військові з’єднання, системи охорони здоров’я, освіти тощо – функціонує заради досягнення певної мети. Усе те, що відбувається в системі, і ступінь досягнення мети, може бути описане математично. І одним з основних інструментів дослідження таких задач ( задач оптимізації) є математичне програмування.
Позначимо через z величину, якою вимірюється ступінь досягнення мети системи, а через - кількісні характеристики, від яких залежить досягнення мети, то зв’язок між і можна подати у вигляді функціональної залежності
(1)
Ця функція називається цільовою функцією або функцією мети.
Завдання математичного програмування полягає в тому, щоб знайти екстремум функції z при обмеженнях, які накладені на змінні :
(2)
Очевидно, що можливості вибору значень практично завжди обмежені. Система нерівностей (2) називається системою обмежень або системою умов задачі.
Зауважимо, що при складанні математичної моделі досліджуваного процесу необхідно дотримуватися загального правила: врахувати все істотне, суттєве в даному явищі чи процесі і відкинути все другорядне.
Множина точок (), що задовольняє систему обмежень (2), називається допустимою множиною або планом задачі математичного програмування. Сукупність усіх розв’язків системи (2), тобто множина всіх планів, утворює область існування планів або область визначення задачі математичного програмування. Допустима множина ( план ), що надає цільовій функції (функції мети) екстремального значення, називається оптимальним. Саме оптимальний план і є розв’язком задачі математичного програмування.
Перехід від постановки задачі до її розв’язку здійснюється за таким алгоритмом:
Побудова математичної моделі задачі – визначення факторів, що вважаються невідомими; побудова системи обмежень; побудова цільової функції на основі умови оптимізації.
Вибір методу розв’язку задачі.
Коригування математичної моделі.
Дослідження отриманого розв’язку і прийняття рішення.
Класифікація задач математичного програмування.
Класифікація задач математичного програмування залежить від критерію, згідно з яким вона проводиться, причому з погляду різних математичних критеріїв та сама задача може належати одночасно до декількох класів, оскільки кожен критерій підкреслює лише одну якість задачі на противагу деякій іншій.
Два основні класи становлять лінійні і нелінійні задачі математичного програмування. Критерієм лінійності задачі є лінійність цільової функції та всіх обмежень. У всіх інших випадках задача буде нелінійною. Перевага лінійних задач у тому, що вони завжди розв’язуються й існують універсальні методи їх розв’язування. Загальних методів розв’язування нелінійних задач не існує. Лише для окремих типів цих задач розроблено спеціальні методи пошуку розв’язку.
Задачі математичного програмування поділяють на дискретні та неперервні. Дискретні – це задачі, в яких усі або деякі змінні набувають дискретних значень. У деяких задачах умову дискретності кожної змінної можна подати умовою цілочисельності цих змінних. Методи розв’язування таких задач увійшли до розділу дискретного або цілочисельного програмування, який належить до нелінійного програмування. Якщо всі змінні задачі можуть набувати всіх значень із деякого інте...
